import { PDAConfiguration, PDARule, Stack } from "./dpda";

class NPDARulebook {
    constructor(
        public rules: PDARule[]
    ) { }

    next_config(configs: PDAConfiguration[], character: string) {
        let nextConfig: PDAConfiguration[] = [];
        configs.forEach(config => {
            // 下一组config
            nextConfig = nextConfig.concat(this.follow_rules_for(config, character))
        })
        return Array.from(new Set(nextConfig));
    }
    follow_rules_for(config: PDAConfiguration, character: string) {
        return this.rules_for(config, character)
            .map(rule => rule.follow(config))
    }
    rules_for(config: PDAConfiguration, character: string) {
        let nextRule: PDARule[] = [];
        this.rules.forEach(rule => {
            if (rule.applies_to(config, character)) {
                nextRule.push(rule)
            }
        })
        return nextRule
    }

    // 自由移动
    follow_free_moves(configs: PDAConfiguration[]) {
        let states = configs.map(config => config.state)
        let more_config = this.next_config(configs, '');
        //检查是否还有
        let checkAll = true;
        for (let index = 0; index < more_config.length; index++) {
            const config = more_config[index];
            if (!states.includes(config.state)) {
                configs.push(config)
                checkAll = false
            }
        }
        if (!checkAll) {
            this.follow_free_moves(configs)
        }
        return configs
    }
}

class NPDA {
    constructor(
        public current_configs: PDAConfiguration[],
        public accept_states: number[],
        public rulebook: NPDARulebook
    ) { 
        this.current_configs = this.rulebook.follow_free_moves(
            this.current_configs
        )
    }

    read_character(character: string) {
        this.current_configs = this.rulebook.next_config(
            this.current_configs, character
        )
        this.current_configs = this.rulebook.follow_free_moves(
            this.current_configs
        )
    }

    read_string(input: string) {
        let inputArray = input.split("");
        inputArray.forEach(s => {
            this.read_character(s)
        })
    }

    accepting() {
        let acceptStates: number[] = [];
        this.current_configs.forEach(config => {
            if (this.accept_states.includes(config.state)) {
                acceptStates.push(config.state)
            }
        })
        return acceptStates.length > 0
    }
}

class NPDADesign{
    constructor(
        public start_state:number,
        public bottom_character:string,
        public accept_states:number[],
        public rulebook:NPDARulebook
    ){}
    
    accepts(input:string){
        let npda = this.to_npda()
        npda.read_string(input)
        return npda.accepting()
    }

    to_npda(){
        let start_stack = new Stack([this.bottom_character])
        let start_config = new PDAConfiguration(this.start_state,start_stack)
        return new NPDA([start_config],this.accept_states,this.rulebook)
    }
}

// let rulebook = new NPDARulebook([
//     new PDARule(1, 'a', 1, '$', ['a', '$']),
//     new PDARule(1, 'a', 1, 'a', ['a', 'a']),
//     new PDARule(1, 'a', 1, 'b', ['a', 'b']),
//     new PDARule(1, 'b', 1, '$', ['b', '$']),
//     new PDARule(1, 'b', 1, 'a', ['b', 'a']),
//     new PDARule(1, 'b', 1, 'b', ['b', 'b']),

//     new PDARule(1, '', 2, '$', ['$']),
//     new PDARule(1, '', 2, 'a', ['a']),
//     new PDARule(1, '', 2, 'b', ['b']),

//     new PDARule(2, 'a', 2, 'a', []),
//     new PDARule(2, 'b', 2, 'b', []),
//     new PDARule(2, '', 3, '$', ['$'])
// ])

// let config = new PDAConfiguration(1,new Stack(['$']))
// let npda = new NPDA([config],[3],rulebook);
// console.log(npda.accepting())
// console.log(npda.current_configs)
// npda.read_string('abb')
// console.log(npda.accepting())
// npda.read_string('a');
// console.log(npda.accepting())

// let npda_design = new NPDADesign(
//     1,'$',[3],rulebook
// )
// console.log(npda_design.accepts('abba'))
// console.log(npda_design.accepts('babbaabbaa'))
// console.log(npda_design.accepts('abb'))
// console.log(npda_design.accepts('baabaa'))

